Resource for Source: C/C++/Resource for Source - C-C++.iso/codelib7/v_09_02/9n02039a

Text File | 1995-11-01 | 5.8 KB | 228 lines

Listing 4.

/* sltest.c */

#define SLTEST  1
#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>
#include "skiplist.h"

/* globals */

int listsize;   /* size of our test list */
int maxlevel = MAXLEVEL;
int partition;
int *emptr; /* dynamic array of list elements */
int nnodes; /* count of nodes allocated */
long ctotals;   /* total number of comparisons */
int comps;  /* temporary counter */
int mincomps;
int maxcomps;
#define COMPMAX 80  /* width of screen */
int compary[COMPMAX] = { 0 };   /* for graph routine */
int overflow = 0;
int levels[MAXLEVEL] = { 0 };
jmp_buf errbuf; /* short circuit when out of memory */
NODE *testlist;
int orderflag;  /* non-zero for random insertions */
#define SL_RAND_MAX 32767

int intcmp(a, b)    /* test comparison routine */
KEYTYPE a, b;
{
    comps += 1; /* track length of search path */
    if(a < b)
        return(-1);
    else if(a == b)
        return(0);
    else
        return(1);
}

main(argc, argv)
int argc;
char *argv[];
{
    if(argc < 6)
        usage();
    if((listsize = atoi(argv[i])) < 1)
        usage();
    if(listsize > SL_RAND_MAX)
    {
        listsize = SL_RAND_MAX;
        printf("listsize reduced to %d\n", SL_RAND_MAX);
    }
    if((maxlevel = atoi(argv[2])) < 1)
        usage();
    if(maxlevel > MAXLEVEL)
    {
        maxlevel = MAXLEVEL;
        printf("maxlevel reduced to %d\n", MAXLEVEL);
    }
    if((partition = atoi(argv[3])) < 1)
        || (partition >= maxlevel))
    {
        usage();
    }
    slsrand((unsigned) atoi(argv[4]));
    orderflag = atoi(argv[5]);

    list_init();
    list_build();
    list_test();
    list_stats();
    exit(EXIT_SUCCESS);
}

usage() /* describe command line errors */
{
    printf("\nUsage:\t");
    printf("sltest <size> <maxlevel> <partition> <seed> <flag>\n");
    printf("\t<size> of test list (>= 1)\n");
    printf("\t<maxlevel> max number of pointers per node (>= 1)\n");
    printf("\t<partition> (>= 1 && < maxlevel [= %d])\n", maxlevel);
    printf("\t<seed> for the random number generator\n");
    printf("\t<flag> 0 for in-order insertions, otherwise random");
    exit(EXIT_FAILURE);
}

list_init()
{
    if((emptr = (int *) calloc(listsize, sizeof(int)))
        == NULL)
    {
        nomem();
    }
    if((testlist = newlist()) == NIL)
        nomem();
}

nomem()
{
    printf("Not enough memory for a list of size %u\n",
        (unsigned)listsize);
    exit(EXIT_FAILURE);
}

list_build()
{
    unsigned slrand();
    unsigned i;

    if(setjmp(errbuf))
        listsize = nnodes;  /* largest possible */
    else if(orderflag == 0)
    {
        for(nnodes = 0, i = 1; i <= listsize; )
            insert(testlist, i++);
    }
    else
    {
        for(nnodes = 0; nnodes < listsize; )
            insert(testlist, slrand());
    }
}

list_test()
{
    int i;

    ctotals = 0L;
    mincomps = listsize;
    maxcomps = 0;
    for(i = 0, comps = 0; i < listsize; ++i, comps = 0)
    {
        search(testlist, emptr[i]);
        ctotals += (long) comps;
        if(comps < mincomps)
            mincomps = comps;
        else if(comps > maxcomps)
            maxcomps = comps;
        if(comps < COMPMAX)
            compary[comps] += 1;
        else
            overflow += 1;  /* won't fit on screen */
    }
}

/* for computing behavior of balanced trees */
unsigned treelevels[] = {
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
    11, 12, 13, 14, 15, 16 };
unsigned powersof2[] = {
    1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,
    4096, 8192, 16384, (SL_RAND_MAX + 1) };
int depth;
long accumulator;

list_stats()    /* print out statistics */
{
    int i;
    int scale;
    int temp;
    int cmax;

    printf("\nskiplist size = %d", listsize);
    printf("\npointers per level = ");
    for(i = 0; i < maxlevel; i += 1)
        printf("%d ", levels[i]);
    printf("\ncomparisons per search:  ");
    printf("mean = %.3f, minimum = %d, maximum = %d\n",
        ((float)ctotals) / ((float)listsize),
        mincomps, maxcomps);
    if(overflow != 0)   /* graph won't fit on screen */
        printf("distribution of comparisons overflows buffer\n");
    else
    {
        cmax = 0;
        for(i = mincomps; i <= maxcomps; i += 1)
        {
            if(compary[i] > cmax)
                cmax = compary[i];
        }
        scale = cmax / 10;
        if(scale == 0)  /* watch out for cmax < 10!! */
            scale = 1;
        temp = cmax % 10;
        if((temp / scale) > 5)
            scale += 1;
        for(temp = cmax; temp >= 0; temp -= scale)
        {
            if(temp <= scale)   /* last pass through */
                if(scale > 1)   /* make sure we */
                    temp = 1;   /* print all */
            for(i = mincomps; i <= maxcomps; i += 1)
            {
                if(compary[i] / temp)
                    printf("*");
                else
                    printf(" ");
            }
            printf("\n");
        }
        printf("distribution from minimum through maximum:");
        printf("  scale = %d:1\n", scale);
    }
    for(i = 0; (powersof2[i] - 1) < listsize; i += 1)
        ;
    depth = i--;    /* maximum for perfectly balanced tree */
    accumulator = ((long) treelevels[i])
        * ((listsize - powersof2[i--]) + 1);
    while(i >= 0)
    {
        accumulator += (long) (treelevels[i]
            * powersof2[i--]);
    }
    printf("for perfect trees:  ");
    printf("mean = %.3f, minimum = 1, maximum = %d\n",
        (((float)accumulator) / ((float)listsize)), depth);
    printf("for degenerate trees:  ");
    printf("mean = %.3f, minimum = 1, maximum = %d\n",
        ((float) (listsize + 1) / 2), listsize);
}

/* EOF */